Computing and communication networks typically include network devices, such as routers, firewalls, switches or gateways, which transfer or switch data, such as packets, from one or more sources to one or more destinations. Network devices may operate on the packets as the packets traverse the network, such as by forwarding or filtering the packet-based network traffic.
A ternary content-addressable memory (TCAM) is commonly used in network devices and other communication devices for quickly identifying content within a packet. A network device may support a number of different features, such as a network device that functions as both a router and a firewall or a router capable of routing both Internet protocol, version 4 (IPv4) and IPv6 routing prefixes. A single TCAM device may be used to support multiple features. With the increasing number of features requiring TCAM support, such as various security and firewall features, deep packet inspection, routing, and tunnel termination features, sharing of a TCAM space can be a cost effective solution for many designs.
A TCAM may be programmed for various types of access control lists (ACLs) (e.g., port ACLs, virtual local area network (VLAN) ACLs, route ACLs, etc.) for both ingress and egress. An ACL may include a set of rules that are explicitly programmed by a network administrator or implicitly programmed by protocols. Each type of ACL is associated with a lookup which corresponds to a database stored in the TCAM. Each database logically belongs to one or more blocks of memory space in the TCAM. With static allocation of the size of each database in the TCAM (e.g., during initialization), a network device or components of a network device are limited by the database size. For example, some databases may overflow with information while other databases may be empty.
Updating an ACL (e.g., adding or deleting a single rule) leads to a large number of rule movements in the TCAM because of the order dependency of the rules. A run mechanism may be used to minimize movement of TCAM rules while updating an ACL. The run mechanism achieves this by maintaining details associated with the run mechanism and by sprinkling (e.g., putting spaces between) rules among available TCAM space (e.g., for a database or for the entire TCAM). The run mechanism can prevent rule movements, but the inherent behavior of sprinkling rules (e.g., throughout an entire TCAM memory space) is very inefficient in terms of power consumption. Power consumed by the TCAM forms a significant part of the power consumed by many network devices. The power consumed by a TCAM depends on how many blocks of memory (e.g., individual units of memory that need to be part of a TCAM lookup cycle) are enabled for lookup.